package com.mlh.binarytree;

//判断是否为二叉排序树/二叉搜索树
public class IsSorted {
    public static boolean sorted(TreeNode head){
        return process(head)[0]==1?true:false;
    }

    //定义一个数组  为所需信息数组
    //arr[0]  1表示为符合二叉排序树  0表示不符合
    //arr[1]  表示树中最大value
    //arr[2]  表示树中最小value
    public static int[] process(TreeNode x){
        if(x==null){
            //遇到一个很棘手的难题，当null时，max和min要返回什么?
            //只能返回一个特殊值，然后针对特殊值，后面的操作要进行判断
            return new int[]{1,-100,-100};
        }

        int[] left=process(x.left);
        int[] right=process(x.right);

        //求出该树的最大和最小value
        int maxVlue;
        int minVlue;
        int res;
        if(left[1]==-100&&right[1]!=-100){
            maxVlue=Math.max(x.val,right[1]);
            minVlue=Math.min(x.val,right[2]);
            res=x.val<right[2]?1:0;
        }else if(left[1]!=-100&&right[1]==-100){
            maxVlue=Math.max(x.val,left[1]);
            minVlue=Math.min(x.val,left[2]);
            res=left[1]<x.val?1:0;
        }else if(left[1]==-100&&right[1]==-100){
            maxVlue=x.val;
            minVlue=x.val;
            res=1;
        }else{
            maxVlue=Math.max(Math.max(x.val,left[1]),right[1]);
            minVlue=Math.min(Math.min(x.val,left[2]),right[2]);
            res=left[1]<x.val&&x.val<right[2]?1:0;
        }
        //判断该树是否为二叉排序树  左max<x.value<右min
        int isSorted=left[0]*right[0]*res;
        return new int[]{isSorted,maxVlue,minVlue};
    }
}
